package com.singzi.leetcode.jianzhiOffer;

import java.util.HashMap;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class T0035 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);
        node1.next.next.next = new Node(55);
        Solution0035 solution0035 = new Solution0035();
        Node node = solution0035.copyRandomList(node1);
        while (node!=null){
            System.out.println(node.val);
            node = node.next;
        }
    }
}

class Solution0035 {
    public Node copyRandomList(Node head) {
        Node s = new Node(head.val);
        Node result = s;
        Node t = head;
        t = t.next;
        while (t!=null){
            s.next = new Node(t.val);
            s = s.next;
            t = t.next;

        }
        Node head0 = head, result0 = result;
        HashMap<Node, Node> nodeHashMap = new HashMap<>();
        while (head != null){
            nodeHashMap.put(head, result);
            head = head.next;
            result = result.next;
        }
        printNode(head0);
        printNode(result0);
        head = head0;
        result = result0;
        while (result0 != null){
            if(head0.random == null) result0.random = null;
            else result0.random = nodeHashMap.get(head0.random);
            result0 = result0.next;
            head0 = head0.next;
        }

        return result;

    }
    public void printNode(Node node){
        System.out.println("-----------");
        while (node!=null){
            System.out.println(node.val);
            node = node.next;
        }
    }

}